home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 3 / Info_Mac_1994-01.iso / Development / Source / Arashi 1.1 Source / For your think c folder / Sound Kit ƒ / Huffman.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-09-09  |  11.4 KB  |  551 lines  |  [TEXT/KAHL]
  1. /*/
  2.      Project Arashi: Huffman.c
  3.      Major release: Version 1.1, 7/22/92
  4.  
  5.      Last modification: Wednesday, September 9, 1992, 21:39
  6.      Created: Saturday, October 6, 1990, 22:34
  7.  
  8.      Copyright © 1990-1992, Juri Munkki
  9. /*/
  10.  
  11. /*
  12. >>    This file contains compression routines for the sound
  13. >>    data of Project STORM. It uses the Huffman algorithm.
  14. */
  15.  
  16. #include "Huffman.h"
  17. #include "Shuddup.h"
  18. #include "asm.h"
  19.  
  20. Handle    PlainHand;        /*    Handle to contain uncompressed sounds.    */
  21. long    PlainSize;        /*    Size when uncompressed.                    */
  22.  
  23. int            MaxCodeLen;    /*    Longest binary coding used.                */
  24. long        MsgBitSize;    /*    Number of bits in the compressed data.    */
  25. Handle        MsgHand;    /*    Compressed data.                        */
  26. treenode    **QuickTable;    /*    Quick lookup table for uncompress.    */
  27.  
  28. treenode    Nodes[VALUES*2];    /*    Huffman encoding tree.            */
  29. treenode    *Sorted[VALUES];    /*    Table of remaining subtrees.    */
  30. int            UsedNodes;            /*    Number of nodes used.            */
  31. int            numsorted;            /*    Number of remaining subtrees.    */
  32.  
  33. /*    Prototypes:
  34. */
  35. treenode *GetSmallest(void);
  36. void CombineNode(treenode *node0, treenode *node1);
  37. void AssignCode(treenode *node, int len, long code);
  38. void DeriveSound(void);
  39. Handle    ReadDataFiles(long ftype);
  40.  
  41. /*
  42. >>    This routine writes the bit patterns in the compressed
  43. >>    form. It's fairly slow on 68000 and 68010 machines, but
  44. >>    works quickly on others.
  45. */
  46. void    OutputPhase()
  47. {
  48.     register    Handle    Outdata;
  49.     register    long    *OutP;
  50.     register    char    *SrcP;
  51.     register    long    bitpos,data;
  52.     register    long    bitwidth;
  53.     register    int        i;
  54.                 long    codes[VALUES];
  55.                 int        lens[VALUES];
  56.     
  57.     Outdata=GetResource(SKRESTYPE,SKHUFFMANN);
  58.  
  59.     SetHandleSize(Outdata,sizeof(long)*VALUES+(MsgBitSize+7)/8);    
  60.     if(!MemErr)
  61.     {    OutP=(long *)*Outdata;
  62.         SrcP=*PlainHand;
  63.         for(i=0;i<VALUES;i++)
  64.         {    *OutP++=Nodes[i].freq;
  65.             codes[i]=Nodes[i].code;
  66.             lens[i]=Nodes[i].codelen;
  67.         }
  68.         bitpos=0;
  69.         
  70.         if(CPUFlag<2)    /*    Incredibly slow version for 68000 & 68010 processors.    */
  71.         {    while(bitpos<MsgBitSize)
  72.             {    data=codes[*SrcP];
  73.                 i=lens[*SrcP++];
  74.                 bitwidth = 1L <<(i-1);
  75.                 
  76.                 while(i--)
  77.                 {    if(data & bitwidth)    BitSet(OutP,bitpos++);
  78.                     else                BitClr(OutP,bitpos++);
  79.                     data <<= 1;
  80.                 }
  81.             }
  82.         }
  83.         else            /*    Much faster version for real processors...            ;-)    */
  84.         {    while(bitpos<MsgBitSize)
  85.             {    data=codes[*SrcP];
  86.                 bitwidth=lens[*SrcP++];
  87.                 asm    68020
  88.                     {    BFINS    data,(OutP){bitpos:bitwidth}
  89.                         add.l    bitwidth,bitpos
  90.                     }
  91.             }
  92.         }
  93.     }
  94.     else
  95.         DebugStr("\PHuffmann failed");
  96.     ChangedResource(Outdata);
  97.     WriteResource(Outdata);
  98. }
  99.  
  100. /*
  101. >>    GetSmallest returns the subtree with the
  102. >>    lowest frequency count. It is used to find
  103. >>    the two lowest counts that are to be combined
  104. >>    into a new subtree.
  105. */
  106. treenode    *GetSmallest()
  107. {
  108.     register    int            i;
  109.     register    int            small;
  110.     register    long        freq;
  111.     register    treenode    *found;
  112.     
  113.     i=small=numsorted-1;
  114.     freq=Sorted[numsorted-1]->freq;
  115.  
  116.     while(i--)
  117.     {    if(Sorted[i]->freq<freq)
  118.         {    small=i;
  119.             freq=Sorted[i]->freq;
  120.         }
  121.     }
  122.     found=Sorted[small];
  123.     Sorted[small]=Sorted[--numsorted];
  124.     return    found;
  125. }
  126. /*
  127. >>    Create a new node out of the two nodes (subtrees)
  128. >>    that are given as parameters.
  129. */
  130. void    CombineNode(node0,node1)
  131. treenode    *node0,*node1;
  132. {
  133.     register    treenode    *newnode;
  134.     
  135.     newnode=&Nodes[UsedNodes++];
  136.     newnode->value=0xFF;
  137.     newnode->codelen=0;
  138.     newnode->code=0;
  139.     newnode->freq=node0->freq+node1->freq;
  140.     newnode->zeroptr=node0;
  141.     newnode->oneptr=node1;
  142.     newnode->typeflag=-1;
  143.     
  144.     Sorted[numsorted++]=newnode;
  145. }
  146. /*
  147. >>    Recursively assigned a binary code
  148. >>    pattern to all nodes. (This is the
  149. >>    final step of the stage that determines
  150. >>    the encoding.)
  151. */
  152. void    AssignCode(node,len,code)
  153. treenode    *node;
  154. int            len;
  155. long        code;
  156. {
  157.     node->code=code;
  158.     node->codelen=len;
  159.     
  160.     if(node->typeflag)
  161.     {    AssignCode(node->zeroptr,len+1,code*2);
  162.         AssignCode(node->oneptr,len+1,code*2+1);
  163.     }
  164.     if(len>MaxCodeLen)
  165.         MaxCodeLen=len;
  166. }
  167. /*
  168. >>    The sound samples are run through this
  169. >>    filter before they are packed. Packing
  170. >>    the differences makes Huffman encoding
  171. >>    much more efficient.
  172. */
  173. void    DeriveSound()
  174. {
  175.     register    long    i;
  176.     register    char    *p;
  177.     register    char    delta,val;
  178.  
  179.     p=*PlainHand;
  180.     for(i=PlainSize;i;i--)
  181.     {    *p= (*p >> DROPBITS) & ANDMASK;
  182.         p++;
  183.     }
  184.  
  185.     p=*PlainHand;
  186.     delta=128>>DROPBITS;
  187.     for(i=PlainSize;i;i--)
  188.     {    val=*p;
  189.         *p++=(val-delta) & ANDMASK;
  190.         delta=val;
  191.     }
  192.     
  193. }
  194. /*
  195. >>    Build a tree out of the frequency
  196. >>    counts. This routine is used for
  197. >>    packing and unpacking of data.
  198. */
  199. void    HuffmannTree()
  200. {
  201.     register    long        i;
  202.     register    treenode    *small1,*small2;
  203.  
  204.     /*    Create pointers for used nodes.
  205.     */
  206.     numsorted=0;
  207.     for(i=0;i<VALUES;i++)
  208.     {    if(Nodes[i].freq)
  209.         {    Sorted[numsorted++]=&Nodes[i];
  210.         }
  211.     }
  212.     
  213.     /*    Huffmann tree generation.
  214.     */
  215.     while(numsorted>1)
  216.     {    small1=GetSmallest();
  217.         small2=GetSmallest();
  218.         CombineNode(small1,small2);
  219.     }
  220.  
  221.     /*    Assign bit strings to tree nodes.
  222.     */
  223.     MaxCodeLen=0;    
  224.     AssignCode(Sorted[0],0,0);
  225.     
  226.     /*    Calculate useful statistics.
  227.     */
  228.     MsgBitSize=0;    /*    Size of output in bits.                    */
  229.     for(i=0;i<VALUES;i++)
  230.     {    MsgBitSize+=Nodes[i].freq*Nodes[i].codelen;
  231.     }
  232. }
  233. /*
  234. >>    Compress the sound files in the current
  235. >>    directory and store the compressed data
  236. >>    in a pair of resources.
  237. */
  238. void    DoCompress()
  239. {
  240.     register    long        i,j;
  241.     register    char        *p;
  242.     
  243.     /*    First, read the data from disk:
  244.     */
  245.     PlainHand=ReadDataFiles(SOUNDFILE);
  246.     PlainSize=GetHandleSize(PlainHand);
  247.     HLock(PlainHand);
  248.  
  249.     /*    Do a delta operation on the sound and divide by 2.
  250.     */
  251.     DeriveSound();
  252.  
  253.     /*    Initialize node values.
  254.     */
  255.     for(i=0;i<VALUES;i++)
  256.     {    Nodes[i].value=i;
  257.         Nodes[i].codelen=0;
  258.         Nodes[i].code=0;
  259.         Nodes[i].freq=0;
  260.         Nodes[i].zeroptr=0;
  261.         Nodes[i].oneptr=0;
  262.         Nodes[i].typeflag=0;
  263.     }
  264.  
  265.     /*    Make a frequency count.
  266.     */
  267.     p=*PlainHand;
  268.     for(i=PlainSize;i;i--)
  269.     {    Nodes[*p++].freq++;
  270.     }
  271.     UsedNodes=VALUES;
  272.  
  273.     /*    Frequency plot in window.
  274.     */    
  275.     for(i=0;i<VALUES;i++)
  276.     {    j=200-(Nodes[i].freq*1000)/PlainSize;
  277.         MoveTo(i,j);
  278.         LineTo(i,j);
  279.     }
  280.  
  281.     /*    Generate the tree and bit strings.
  282.     */
  283.     HuffmannTree();
  284.  
  285.     if(MaxCodeLen<=32)
  286.     {    OutputPhase();
  287.     }
  288.     else
  289.     {    SysBeep(10);    /*    This should never happen.    */
  290.         DebugStr("\PHuffmann failed.");
  291.     }
  292.     HUnlock(PlainHand);
  293.     DisposHandle(PlainHand);
  294. }
  295. /*
  296. >>    DeCompress only handles the more generic part
  297. >>    of the sound decompression. It reads the packed
  298. >>    data and frequency counts. The frequency counts
  299. >>    are used to rebuild the same tree that was used
  300. >>    for compression. A fast lookup table is then
  301. >>    built so that multiple bits can be decoded at
  302. >>    once.
  303. */
  304. void    DeCompress()
  305. {    
  306.     register    long    *MsgPtr;
  307.     register    long    i,j;
  308.             treenode    *TheNode;
  309.  
  310.     QuickTable=(treenode **)NewPtr(sizeof(treenode)*(1<<QTBITS));
  311.     MsgHand=GetResource(SKRESTYPE,SKHUFFMANN);
  312.     HLock(MsgHand);
  313.     MsgPtr=(long *)*MsgHand;
  314.     
  315.     PlainSize=0;
  316.     /*    Initialize node values.
  317.     */
  318.     for(i=0;i<VALUES;i++)
  319.     {    Nodes[i].value=i;
  320.         Nodes[i].codelen=0;
  321.         Nodes[i].code=0;
  322.         Nodes[i].freq=*MsgPtr++;
  323.         Nodes[i].zeroptr=0;
  324.         Nodes[i].oneptr=0;
  325.         Nodes[i].typeflag=0;
  326.         
  327.         PlainSize+=Nodes[i].freq;
  328.     }
  329.     UsedNodes=VALUES;
  330.  
  331.     /*    Generate the tree and bit strings.
  332.     */
  333.     HuffmannTree();
  334.  
  335.     /*    Set up a table for quick access for the QTBITS first levels
  336.     **    of the tree.
  337.     */
  338.     for(i=0;i<(1<<QTBITS);i++)
  339.     {    QuickTable[i]=0;
  340.     }
  341.     for(i=UsedNodes;i>=0;i--)
  342.     {    if(Nodes[i].freq && Nodes[i].codelen<=QTBITS)
  343.         {    QuickTable[Nodes[i].code<<(QTBITS-Nodes[i].codelen)]=&Nodes[i];
  344.         }
  345.     }
  346.  
  347.     for(i=0;i<(1<<QTBITS);i++)
  348.     {    if(QuickTable[i])        TheNode=QuickTable[i];
  349.         else                    QuickTable[i]=TheNode;
  350.     }
  351.     
  352. }
  353. /*
  354. >>    This routine first runs the previous one
  355. >>    and then uses the tree and the lookup table
  356. >>    to decode the data. Every sound is also
  357. >>    processed so that it can be efficiently
  358. >>    played with the sound kit.
  359. */
  360. void    DecodeSounds()
  361. {
  362.                 Handle        sinfo;
  363.                 Ptr            sdatap;
  364.                 long        *infop;
  365.                 int            i;
  366.  
  367.                 treenode    **QTable;
  368.     register    treenode    *TheNode;
  369.     register    Ptr            MsgData;
  370.  
  371.     register    long        bitpos,data;
  372.     register    long        count;
  373.     register    char        delta;
  374.     register    long        len;
  375.  
  376.                 int            sampleframes;
  377.                 int            samplepad;
  378.  
  379.     
  380.     if(OldSound)            /*    The sounds are padded so that they in samplepad-sized packets.    */
  381.     {    sampleframes=185;    /*    Each packet contains samplesframes bytes of data.                */
  382.         samplepad=188;
  383.     }
  384.     else
  385.     {    sampleframes=512;    /*    If the sound manager is used, no padding is necessary, but the    */
  386.         samplepad=512;        /*    sound length has to be a multiple of 512.                        */
  387.     }
  388.  
  389.     QTable=QuickTable;
  390.  
  391.     sinfo=GetResource(SKRESTYPE,SKSTABLE);
  392.     NumSounds=GetHandleSize(sinfo)/sizeof(long);
  393.     HLock(sinfo);
  394.     infop=(long *)*sinfo;
  395.  
  396.     len=0;
  397.     for(i=0;i<NumSounds;i++)
  398.     {    len+=((infop[i]+(sampleframes-1))/sampleframes)*samplepad;
  399.     }
  400.     
  401.     HUnlock(MsgHand);
  402.  
  403.     SKPtr=NewPtr(len+sizeof(SoundStuff)*(long)NumSounds);
  404.     if(MemErr)
  405.     {    NumSounds=0;
  406.         return;
  407.     }
  408.  
  409.     HLock(MsgHand);
  410.     MsgData=(sizeof(long)*VALUES)+*MsgHand;
  411.  
  412.     Sounds=(void *)SKPtr;
  413.     sdatap=SKPtr+sizeof(SoundStuff)*(long)NumSounds;
  414.     
  415.     for(i=0;i<NumSounds;i++)
  416.     {    len=((infop[i]+(sampleframes-1))/sampleframes)*samplepad;
  417.         Sounds[i].Poin=sdatap;
  418.         Sounds[i].Len=len;
  419.         Sounds[i].Count=len/samplepad;
  420.         sdatap+=len;
  421.     }
  422.  
  423.     delta=128>>DROPBITS;
  424.     bitpos=0;
  425.  
  426.     for(i=0;i<NumSounds;i++)
  427.     {    sdatap=Sounds[i].Poin;
  428.         len=infop[i];
  429.         count=sampleframes;
  430.  
  431.         if(CPUFlag<2)        /*    Check for processor type.                */
  432.         {    while(len--)    /*    Version for 68000 and 68010 processors.    */
  433.             {
  434.                 asm
  435.                     {    cmp.b    #16,bitpos
  436.                         blt.s    @nobitshift
  437.                         sub.b    #16,bitpos
  438.                         lea        2(MsgData),MsgData
  439.                     @nobitshift
  440.                         move.l    (MsgData),data
  441.                         move.l    bitpos,D0
  442.                         add.b    #QTBITS,D0
  443.                         rol.l    D0,data
  444.                         and.l    #((1<<QTBITS)-1),data
  445.                     }
  446.                     TheNode=QTable[data];
  447.     
  448.                 if(TheNode->typeflag)
  449.                 {    bitpos+=QTBITS;
  450.                     asm    {
  451.                     @begin0        cmp.b    #16,bitpos
  452.                                 blt.s    @nobitshifteither
  453.                                 sub.b    #16,bitpos
  454.                                 lea        2(MsgData),MsgData
  455.                     @nobitshifteither
  456.                                 move.l    (MsgData),data
  457.                                 addq.l    #1,bitpos
  458.                                 rol.l    bitpos,data
  459.                                 bcc.s    @zeropoint0
  460.                             
  461.                                 move.l    OFFSET(treenode,oneptr)(TheNode),TheNode
  462.                                 move.w    OFFSET(treenode,typeflag)(TheNode),D0
  463.                                 bne.s    @begin0
  464.                                 bra.s    @loopdone0
  465.                     @zeropoint0    move.l    OFFSET(treenode,zeroptr)(TheNode),TheNode
  466.                                 move.w    OFFSET(treenode,typeflag)(TheNode),D0
  467.                                 bne.s    @begin0
  468.                     @loopdone0        
  469.                     }
  470.                 }
  471.                 else
  472.                 {    bitpos+=TheNode->codelen;
  473.                 }
  474.                 delta+=TheNode->value;
  475.                 delta&=ANDMASK;
  476.                 *sdatap++=delta;
  477.                 if(!--count)
  478.                 {    count=samplepad-sampleframes;
  479.                     while(count--)
  480.                         *sdatap++=delta;
  481.     
  482.                     count=sampleframes;
  483.                 }
  484.             }
  485.             
  486.             if(count!=sampleframes)
  487.             {    count=(count+samplepad-sampleframes) % samplepad;
  488.                 while(count--)
  489.                 {    *sdatap++=delta;
  490.                 }
  491.             }
  492.         }
  493.         else    /*    Version for 68020, 68030, 68040 processors    */
  494.         {    while(len--)
  495.             {
  496.                 asm    68020
  497.                     {
  498.                     bfextu    (MsgData){bitpos:QTBITS},data
  499.                     }
  500.                     TheNode=QTable[data];
  501.     
  502.                 if(TheNode->typeflag)
  503.                 {    bitpos+=QTBITS;
  504.                     asm    68020
  505.                     {
  506.                     @begin
  507.                                 bfextu    (MsgData){bitpos:1},data
  508.                                 beq.s    @zeropoint
  509.                                 move.l    OFFSET(treenode,oneptr)(TheNode),TheNode
  510.                                 addq.l    #1,bitpos
  511.                                 move.w    OFFSET(treenode,typeflag)(TheNode),D0
  512.                                 bne.s    @begin
  513.                                 bra.s    @loopdone
  514.                     @zeropoint    move.l    OFFSET(treenode,zeroptr)(TheNode),TheNode
  515.                                 addq.l    #1,bitpos
  516.                                 move.w    OFFSET(treenode,typeflag)(TheNode),D0
  517.                                 bne.s    @begin
  518.                     @loopdone        
  519.                     }
  520.                 }
  521.                 else
  522.                 {    bitpos+=TheNode->codelen;
  523.                 }
  524.                 delta+=TheNode->value;
  525.                 delta&=ANDMASK;
  526.                 *sdatap++=delta;
  527.                 if(!--count)
  528.                 {    count=samplepad-sampleframes;
  529.                     while(count--)
  530.                         *sdatap++=delta;
  531.     
  532.                     count=sampleframes;
  533.                 }
  534.             }
  535.             
  536.             if(count!=sampleframes)
  537.             {    count=(count+samplepad-sampleframes) % samplepad;
  538.                 while(count--)
  539.                 {    *sdatap++=delta;
  540.                 }
  541.             }
  542.         }
  543.     }
  544.     
  545.     HUnlock(sinfo);
  546.     ReleaseResource(sinfo);
  547.     HUnlock(MsgHand);
  548.     ReleaseResource(MsgHand);
  549.     DisposPtr(QuickTable);    
  550. }
  551.